package treeStudy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AverageOfLevels {

    /**
     * LeetCode T637 二叉树的层平均
     *
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
     * @param args
     */
    public static void main(String[] args) {

    }

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        int level = 1;
        int count = 0;
        double sum = 0;
        queue.offer(new Node(root.val, 1, root));
        while (!queue.isEmpty()){
            Node node = queue.poll();
            if (node.level == level){
                count++;
                sum += node.value;
            } else {
                //更新一下
                level = node.level;
                ans.add((sum/count));
                sum = node.value;
                count = 1;
            }
            if (node.ptr.left != null){
                queue.offer(new Node(node.ptr.left.val, node.level + 1, node.ptr.left));
            }
            if (node.ptr.right != null){
                queue.offer(new Node(node.ptr.right.val, node.level + 1, node.ptr.right));
            }
        }
        if (count != 0){
            ans.add((sum/count));
        }
        return ans;
    }
}
class Node{
    int value;
    int level;
    TreeNode ptr;

    Node(){

    }

    Node(int value, int level, TreeNode ptr) {
        this.value = value;
        this.level = level;
        this.ptr = ptr;
    }
}
